Maximum profit in job scheduling [DP, Heap]

Time: O(NLogN); Space: O(N); hard

We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i].

You’re given the startTime , endTime and profit arrays, you need to output the maximum profit you can take such that there are no 2 jobs in the subset with overlapping time range.

If you choose a job that ends at time X you will be able to start another job that starts at time X.

Example 1:

Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]

Output: 120

Explanation:

  • The subset chosen is the first and fourth job.

  • Time range [1-3]+[3-6] , we get profit of 120 = 50 + 70.

Example 2:

Input: startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]

Output: 150

Explanation:

  • The subset chosen is the first, fourth and fifth job.

  • Profit obtained 150 = 20 + 70 + 60.

Example 3:

Input: startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]

Output: 6

Constraints:

  • 1 <= len(startTime) = len(endTime) = len(profit) <= 5 * 10^4

  • 1 <= startTime[i] < endTime[i] <= 10^9

  • 1 <= profit[i] <= 10^4

Hints:

  1. Think on DP.

  2. Sort the elements by starting time, then define the dp[i] as the maximum profit taking elements from the suffix starting at i.

  3. Use binarySearch (lower_bound/upper_bound on C++) to get the next index for the DP transition.

1. Dynamic programming [O(NLogN), O(N)]

[9]:

import bisect

class Solution1(object):
    """
    Time: O(NLogN)
    Space: O(N)
    """
    def jobScheduling(self, startTime, endTime, profit):
        """
        :type: startTime: List[int]
        :type: endTime: List[int]
        :type profit: List[int]
        :rtype: int
        """
        jobs = sorted(zip(endTime, startTime, profit))
        dp = [(0, 0)]

        for e, s, p in jobs:
            i = bisect.bisect_right(dp, (s+1, 0))-1
            if dp[i][1]+p > dp[-1][1]:
                dp.append((e, dp[i][1]+p))

        return dp[-1][1]

[10]:

s = Solution1()

startTime = [1,2,3,3]
endTime = [3,4,5,6]
profit = [50,10,40,70]
assert s.jobScheduling(startTime, endTime, profit) == 120

startTime = [1,2,3,4,6]
endTime = [3,5,10,6,9]
profit = [20,20,100,70,60]
assert s.jobScheduling(startTime, endTime, profit) == 150

startTime = [1,1,1]
endTime = [2,3,4]
profit = [5,6,4]
assert s.jobScheduling(startTime, endTime, profit) == 6

2. Heap [O(NLogN), O(N)]

[13]:

import heapq

class Solution2(object):
    """
    Time: O(NLogN)
    Space: O(N)
    """
    def jobScheduling(self, startTime, endTime, profit):
        """
        :type: startTime: List[int]
        :type: endTime: List[int]
        :type profit: List[int]
        :rtype: int
        """
        min_heap = list(zip(startTime, endTime, profit))
        heapq.heapify(min_heap)
        result = 0

        while min_heap:
            s, e, p = heapq.heappop(min_heap)
            if s < e:
                heapq.heappush(min_heap, (e, s, result+p))
            else:
                result = max(result, p)
        return result

[14]:

s = Solution2()

startTime = [1,2,3,3]
endTime = [3,4,5,6]
profit = [50,10,40,70]
assert s.jobScheduling(startTime, endTime, profit) == 120

startTime = [1,2,3,4,6]
endTime = [3,5,10,6,9]
profit = [20,20,100,70,60]
assert s.jobScheduling(startTime, endTime, profit) == 150

startTime = [1,1,1]
endTime = [2,3,4]
profit = [5,6,4]
assert s.jobScheduling(startTime, endTime, profit) == 6